COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002				PROPOSED ITER FACILITY
C00019 00003	ββββ
C00020 ENDMK
C⊗;
			PROPOSED ITER FACILITY

	LISP'S DO facility is baroquely powerful.  Here we propose a
facility even more baroquely powerful.  It addresses two shortcomings
of DO:  no input streams and no output streams.  Ideally DO should
conveniently subsume all 6 MAP facilities, which offer a fair
treatment of input and output streams.  Unfortunately it does not, and
simulating MAPCAR with DO is quite awkward.  The following remedies
this.  Criticisms and counter-proposals solicited.  When the hue and
cry has died down I will implement ITER as a macro and make it
available on LIBLSP.  Whether ITER will eventually achieve parity with
DO and become known to the compiler presumably depends on whether
people find it useful.

FORMAT

	To begin, let us give a fairly general example of an ITER.

(ITER ((L I) ((TO 15) J))
      (((ADD1 I) P) ((PRINT (PLUS I J)) NIL))
      (EQUAL ITER-COUNT 10)
      (CDR P))

	This ITER has four arguments.  The first is rather like DO's
first argument.  There are two input streams, the list L and the
interval (TO 15).  I and J are the controlled variables that step
through these respective streams.  The second argument specifies what
the results are and where they go.  In this case, at each iteration
the current value of I is incremented and sent to a stream called P. 
Also the sum of I and J are printed and the resulting value is sent to
the NIL stream, i.e. is discarded.  The third argument specifies when
to stop.  If it evaluates to true before any of the sources (here L
and (TO 15)) have been exhausted, then the iteration stops and the
fourth argument is evaluated and the resulting value returned as the
value of the ITER.  In this case it is the cdr of the stream that had
been accumulating the incremented I's, so if L had been initially (1 2
3 4 1 2 3 4 1 2 3 4) then the result would have been (3 4 5 2 3 4 5 2
3).  Moreover, the numbers 2 4 6 8 12 8 10 12 10 12 will have been
printed out (assuming BASE is 10. and *NOPOINT is T).

	Having seen a particular example, we now proceed to a more
formal treatment.  ITER is a macro that may take any number of
arguments.  The general form (with defaults written below each
argument) is

(ITER <input-list> <output-list> <end-test> ... <answer>)
	NIL		NIL	    NIL		ITER-RESULT

	The input-list approximates DO's first argument, except that
it is more stream oriented.  The output list is a sort of dual of the
input list, making it easy to stream output to various sinks. 
Normally ITER terminates when an input source is exhausted; however,
if end-test ever evaluates to true then ITER will terminate forthwith.
On termination (however caused), the remaining arguments of ITER
following the end-test are evaluated and the value of the last is the
value of the ITER.

	ITER maintains three variables lambda-bound inside the ITER. 
They are ITER-COUNT which gives the number of iterations so far
(initially 0), ITER-STOP which specifies the reason for termination by
having value either NIL (end-test) or one of the input variables
associated with an exhausted source, and ITER-RESULT whose value is
the default value returned by the ITER (in many applications it will
not need to be named explicitly anywhere in the ITER).

	An input (i.e. an element of the input-list) is a list of one
to three items:

(<source> <input-variable> <source-type>)
		none		NIL

	The input variable when present should always be atomic.  (It
is written after the source both for consistency with the output
format where the items are written in the order in which the data
flows, and to permit omitting the input variable.)  The source should
be some kind of stream.  One source-type is a LIST.  The elements from
this list are those that MAPC produces.  To get the effect of MAP, use
the source-type CDR.  Another source-type is an INTERVAL, specified by
the form:

(TO <upper-limit> <lower-limit> <step-size>)
      infinity	        1	      1

(Again the defaults are given below.)  The source-type for this source
is INTERVAL.  The form (TO x y z) does not need to be quoted because
TO has as its macro property the superquoting macro (LAMBDA (X) (LIST
'QUOTE X)).

	Another source-type is GENERATOR, also having the superquoting
macro property, with format

(GENERATOR <initial-value> <step-function> <empty-predicate>)
					    (LAMBDA (X) NIL)

which yields first its initial value then the result of applying the
step function to the most recent value.  The empty predicate defines
when this source is empty and takes as argument the next value to be
emitted.  Thus one could define (TO a b c) as
(GENERATE b (LAMBDA (X) (PLUS X c)) (LAMBDA (X) (GREATERP X b))). 

	When the source-type is not known, NIL (the default) may be
supplied in which case the ITER will check the type at run time,
allowing streams to have first-class-citizen behavior.

	The output list is a fair dual of the input list.  The format
of an output element is:

(<output-item> <sink> <sink-init>    	<sink-type>)
		 T	  NIL   (LAMBDA (X Y) (NCONC X (LIST Y)))

	An output item can be any expression.  A sink should be an
atomic symbol; NIL denotes the bottomless sink (output discarded)
while T denotes ITER-RESULT.  The sink-init is the initial value of
the sink.  The sink-type should be a function of two arguments.  The
first argument will be bound to the current value of the sink, the
second to the current value of the output-item, and the result is the
new value of the sink.  Note that sink variables are lambda-bound by
the ITER (call it currying favor with the CLU hackers if you will - I
am open to debate on this obviously controversial aspect).

	END-TEST is self-explanatory, as is ANSWER.

			SEMANTICS OF ITER

	The following supplies an informal interpretive semantics for
ITER.  It has three phases, prologue, cycle, epilogue.

PROLOGUE

ITER-COUNT is lambda-bound to 0, ITER-RESULT and ITER-STOP are
lambda-bound to NIL, and all sinks are lambda-bound to their initial
values.

CYCLE

Iterate the following steps

1.  All input sources are tested for emptiness in the order given.  On
encountering an empty source, ITER-STOP is SETQ'd to its input
variable and the cycle terminates.

2.  All input variables are bound to their next source element.

3.  End-test is evaluated.  If true, the cycle terminates.

4.  All output items are evaluated and sent to their respective next
source element.  The sending is completed for one sink before
proceeding to the next output element.  (Maybe it is better to get all
the output values in parallel, then send them?)

5.  ITER-COUNT is incremented.

EPILOGUE

The 4th, 5th, etc arguments to ITER are evaluated and the value of the
last is then returned as the value of the ITER.

If at any time within the ITER (RETURN x) is evaluated, then the
least ITER, DO or PROG containing that RETURN immediately returns the
value of x.

			EXAMPLES

(ITER)

Useful for warming up the computer on a cold day prior to changing its
oil.

(ITER ((L I)) (((PRINT I))))

This prints the elements of the list L.  For this you may as well use
(MAPCAR 'PRINT L).  Obviously you intended to do (MAPC 'PRINT L), so
instead do

(ITER ((L I)) (((PRINT I) NIL)))

which sends the value returned by each PRINT to the bottomless sink. 
The value of this ITER will be NIL, so it is not exactly MAPC.

(ITER () (((PRINT 'DRINK) NIL)))

Prints an endless supply of drinks.  Useful for when you're having
more than one.

(ITER ((L I LIST) (M J LIST)) (((PLUS I J))))

Identical to (MAPCAR 'PLUS L M).  The presence of LIST simply tells
ITER that it can assume that L and M are bound to lists as opposed to
intervals or generators, saving run-time type-checking.  The user will
never go wrong omitting LIST - it is purely a concession to efficiency.

(ITER (((TO 10) I)) (((PROGN (PRINT I) (PRIN1 (TIMES I I))) NIL))) 

	This prints out a column of the numbers from 1 to 10 with their
squares beside them.  The input element could have been written ((TO
10) I INTERVAL), but ITER can see this for itself so it is quite
redundant.  If the output element had been (X I INTERVAL) then ITER
would have known that X should evaluate to an interval, which saves a
little type-checking.

(ITER (((TO) I) (M J)) (((PLUS I J))))

	Forms a list which is M with its i-th element incremented by
i.  This works by I counting up to infinity while J is scanning
through M.  As soon as M is exhausted the process stops.

(ITER ((L I)) () (P I) I)

	This searches a list for an element satisfying the predicate P
and returns the first one it finds, or nil if it finds none.

(ITER (((TO 10))) ((a NIL)))

	Does a 10 times.

(ITER (((TO 10))) (('GREEN/ BOTTLES)))

	A list of 10 green bottles.

(ITER () ((a NIL)) b)

	This has the effect of "while b do a".  Not quite as
convenient as (DO () (b) a).

(ITER () ((a NIL)) (AND (PLUSP ITER-COUNT) b))

	One way to get the effect of "repeat a until b".

(ITER (((TO N) I)) ((I T 1 TIMES)))

	Yet another way of computing factorial(N).  (!)

(SETQ X (ITER ((Y I)) ((I T X))))

Has the same effect as (SETQ X (NCONC X Y)) except that in effect a
copy of Y is made..

(ITER ((L I) (M J)) (((QUOTIENT I J) X) ((REMAINDER I J) Y)) () (LIST X Y))

	This returns a two-element list with first element a list of
the quotients of corresponding elements of M and N and second element
the remainders.

(DEFUN CONVOLVE (A B)		; convolution of vectors A and B
(PROG (RA CB)
      (SETQ RA (REVERSE A) CB (APPEND B NIL))
      (RPLACD (LAST CB) B)                ; makes CB circular
      (ITER (((CDR CB) X CDR))
            (((ITER ((RA I) (X J))
                    (((TIMES I J) T 0 PLUS)))))
            (AND (PLUSP ITER-COUNT) (EQ (CDR X) CB)))))

This defines the circular convolution of two vectors A and B
represented as two equal-length lists of numbers.  The convolution is
defined so that if the vectors are (A0,A1,...,A(n-1)) and
(B0,B1,...B(n-1)) then the k-th element of the convolution (again
numbering from 0) is Ck = Ai*Bj summed over all i,j satisfying i+j=k (mod n).


   

	I welcome further examples.

ββββ